//
//  103. 二叉树的锯齿形层序遍历.swift
//  Top600
//
//  Created by rjb on 2021/8/8.
//

import Foundation
class Solution103 {
    // 采用层序遍历
    func zigzagLevelOrder(_ root: TreeNode?) -> [[Int]] {
        guard let root = root else {
            return []
        }
        var queue: [TreeNode] = []
        queue.append(root)
        var flag = true
        var result: [[Int]] = []
        while !queue.isEmpty {
            var size = queue.count
            var array: [Int] = []
            while size > 0 {
                let first = queue.removeFirst()
                size -= 1
                if flag {
                    array.append(first.val)
                } else {
                    array.insert(first.val, at: 0)
                }
                if let left = first.left {
                    queue.append(left)
                }
                if let right = first.right {
                    queue.append(right)
                }
            }
            flag = !flag
            result.append(array)
        }
        return result
    }
    static func test() {
        let solution = Solution103()
        
        let node3 = TreeNode(3)
        let node9 = TreeNode(9)
        let node20 = TreeNode(20)
        let node15 = TreeNode(15)
        let node7 = TreeNode(7)
        
        node3.left = node9
        node3.right = node20
        node20.left = node15
        node20.right = node7
        
        let result = solution.zigzagLevelOrder(node3)
        print(result)
    }
}
